# set创建一个无序不重复的数据集
# http://www.runoob.com/python/python-func-set.html
class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        if not board or not words:
            return []

        # build trie,建立了一个简单的前缀树
        trie = {}
        for w in words:
            t = trie
            for c in w:
                if c not in t:
                    t[c] = {}
                t = t[c]
            t['#'] = '#'

        self.res = set()
        self.row = len(board)
        self.col = len(board[0]) if self.row else 0

        def dfs(x, y, node, path):
            if '#' in node:
                self.res.add(path)
            if x < 0 or x >= self.row or y < 0 or y >= self.col:
                return
            if board[x][y] in node:
                c = board[x][y]
                board[x][y] = '*'  # backtracking
                dfs(x + 1, y, node[c], path + c)
                dfs(x - 1, y, node[c], path + c)
                dfs(x, y + 1, node[c], path + c)
                dfs(x, y - 1, node[c], path + c)
                board[x][y] = c# 在以该点为起点的路径遍历完之后会变为原值

        for i in range(self.row):
            for j in range(self.col):
                dfs(i, j, trie, '')

        return list(self.res)






# 复杂度超了，对于相同前缀的字符不能识别
class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        if not board:
            return []
        m = len(board)
        n = len(board[0])
        res = []
        for word in words:
            dp = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if board[i][j] == word[0]:

                        dp[i][j] = 1
                        if self.dfs(dp, board, word[1:], i, j):
                            res.append(word)
                            break
                        dp[i][j] = 0
                else:
                    continue
                break
        return res

    def dfs(self, dp, board, word, i, j):
        if not word:
            return True
        m = len(board)
        n = len(board[0])
        if i < m - 1 and board[i + 1][j] == word[0] and not dp[i + 1][j]:
            dp[i + 1][j] = 1
            if self.dfs(dp, board, word[1:], i + 1, j):
                return True
            dp[i + 1][j] = 0
        if i > 0 and board[i - 1][j] == word[0] and not dp[i - 1][j]:
            dp[i - 1][j] = 1
            if self.dfs(dp, board, word[1:], i - 1, j):
                return True
            dp[i - 1][j] = 0
        if j < n - 1 and board[i][j + 1] == word[0] and not dp[i][j + 1]:
            dp[i][j + 1] = 1
            if self.dfs(dp, board, word[1:], i, j + 1):
                return True
            dp[i][j + 1] = 0
        if j > 0 and board[i][j - 1] == word[0] and not dp[i][j - 1]:
            dp[i][j - 1] = 1
            if self.dfs(dp, board, word[1:], i, j - 1):
                return True
            dp[i][j - 1] = 0
        return False


# 可通过，自己写的
class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        self.res = []
        tire = dict()
        for word in words:
            t = tire
            for i in range(len(word)):
                if word[i] not in t:
                    t[word[i]] = dict()
                t = t[word[i]]
            t['#'] = '#'
        m = len(board)
        n = len(board[0])
        dp = [[0] * n for i in range(m)]
        for i in range(m):
            for j in range(n):
                 if board[i][j] in tire:
                     path = board[i][j]
                     dp[i][j] = 1
                     self.dfs(board, dp, tire[board[i][j]], i, j, path)
                     dp[i][j] = 0
        return list(set(self.res))
    def dfs(self, board, dp, tire, i, j, path):
        if '#' in tire:
            self.res.append(path)
        m = len(board)
        n = len(board[0])
        if i < m-1 and board[i+1][j] in tire and not dp[i+1][j]:
            dp[i+1][j] = 1

            self.dfs(board, dp, tire[board[i+1][j]], i+1, j, path+board[i+1][j])
            dp[i+1][j] = 0
        if i > 0 and board[i-1][j] in tire and not dp[i-1][j]:
            dp[i-1][j] = 1

            self.dfs(board, dp, tire[board[i-1][j]], i-1, j, path + board[i-1][j])

            dp[i-1][j] = 0
        if j < n-1 and board[i][j+1] in tire and not dp[i][j+1]:
            dp[i][j+1] = 1

            self.dfs(board, dp, tire[board[i][j+1]], i, j+1, path + board[i][j+1])

            dp[i][j+1] = 0
        if j > 0 and board[i][j-1] in tire and not dp[i][j-1]:
            dp[i][j-1] = 1

            self.dfs(board, dp, tire[board[i][j-1]], i, j-1, path + board[i][j-1])
            dp[i][j-1] = 0

